package practice_2025_9.practice_9_11;

class Solution {
    /**
     * 接雨水
     * @param height
     * @return
     */
    public int trap(int[] height) {
        // 一共可以接多少雨水
        // 每一列可以接的雨水：宽度（1） * (min(左边最大高度, 右边最大高度) - 当前高度)
        int n = height.length;
        int[] left = new int[n]; // i 位置左边 [0, i - 1] 最大高度
        int[] right = new int[n]; // i 位置右边[i + 1, n - 1] 最大高度
        for(int i = 1; i < n; i++) {
            left[i] = Math.max(height[i - 1], left[i - 1]);
        }
        for(int i = n - 2; i > 0; i--) {
            right[i] = Math.max(height[i + 1], right[i + 1]);
        }
        int sum = 0;
//        System.out.println(Arrays.toString(left));
//        System.out.println(Arrays.toString(right));
        // 0 和 n - 1 没有另一边，不需要计算
        for(int i = 1; i < n - 1; i++) {
            int l = Math.min(left[i], right[i]);
            if (l > height[i]){
                sum += (l - height[i]);
            }
            

        }
        return sum;
    }
}